1. Field of the Invention
The invention relates to circuits used to perform computations on the elements of a Galois field denoted GF(2.sup.n) and especially a circuit enabling computation of operations of division in such a field.
2. Description of the Prior Art
A Galois field is a finite set of binary numbers used, for example, to correct errors in data transmission implementing Reed-Solomon encoding and decoding operations. The set of binary numbers of n bits, n being an integer, forms a Galois field of 2.sup.n =N elements, on which an internal addition and multiplication are defined, i.e. in such a way that the sum or the product of two numbers of the field is also a number of the field. The addition of two numbers consists of the performance of an XOR (or Exclusive-OR) operation bit by bit between these two numbers. The result thereof is that if any element x of the field is considered, then x+x=2.x=0. The multiplication is a standard multiplication of two binary numbers of n bits so long as it generates no carry value, namely so long as the result includes no bits at 1 with a place value greater than n-1. Once a carry value is generated, it is combined by an XOR operation with predetermined bits of the bits with place values 0 to n-1 defined by a polynomial known as the Galois field generator polynomial.
Any non-zero element of the Galois field is a power of another element of this field that is not zero and not unity. In a Galois field with N+1 elements, these power values are defined modulo-N, namely x.sup.i =x.sup.i+N, with x as an element of the Galois field that is not zero and not unity and i as a positive or negative integer. The elements of a Galois field of N+1 elements are 0, .alpha..sup.0, .alpha..sup.1, . . . , .alpha..sup.N-1. The elements .alpha..sup.0 to .alpha..sup.N-1 are the numbers 2.sup.0, 2.sup.1, . . . 2.sup.n-1 constituting the base of the binary numbers of n bits.
In certain applications, it becomes necessary to perform operations of division. Thus, for example, to compute correction coefficients in a Reed-Solomon decoder, it is necessary to compute ratios A/B where A and B are numbers computed by the decoder and capable of assuming any value. At present, there are no simple dividers that can be used to perform a division directly. To compute A/B, A is generally multiplied by the reciprocal of B.
To compute a reciprocal, generally, a table of reciprocals is used. This table is stored in a ROM memory dedicated to this use. However the use of a ROM memory does not lend itself well to an integration with the other processing circuits in present-day techniques for the designing of integrated circuits. With these techniques, the ROM memory must be placed outside a zone in which the other elements of the processing circuit are integrated. This leads to a substantial loss of surface area even if this ROM memory takes up a relatively small surface area (for example if 8 bits words are used, the memory will contain 256 words, which is little).